Fair bandwidth sharing at routers has several advantages, including protection of well-behaved flows and possible simplification of end-to-end congestion control mechanisms. Traditional mechanisms to achieve fair sharing (e.g., Weighted Fair Queueing, Flow Random Early Discard) require per-flow state to determine which packets to drop under congestion, and therefore are complex to implement at the interior of a high-speed network.
Weighted Fair Queueing (WFQ) as a mechanism to achieve fair bandwidth sharing and delay bounds has been described by “Analysis and Simulation of a Fair Queueing Algorithm,” by A. Demers et al., SIGCOMM Symposium on Communications Architectures and Protocols, September 1989, and A Generalized Processor Sharing Approach to Flow Control In Integrated Services Networks, Ph.D. thesis, Laboratory for Information and Decision Systems, Massachusetts Institute of Technology, February 1992. Strict WFQ is, however, generally considered too complex to implement in practice. Many variants of the WFQ algorithm have been proposed, with different tradeoffs between complexity and accuracy. See, for example, “Efficient Fair Queuing using Deficit Round Robin,” by M. Shreedhar et al., in Proceedings of SIGCOMM '95, September 1995, “Hierarchical Packet Fair Queueing Algorithms,” by Jon C. R. Bennett. et al., in Proceedings of SIGCOMM '96, August 1996 and “A Self-clocked Fair Queueing Scheme for Broadband Applications,” by S. Golestani in Proceedings of IEEE INFOCOM '94, June 1994. Nevertheless, the WFQ computation is only part of the task; a per-flow queueing system also requires flow classification and per-flow state maintenance. Every incoming packet has to be classified to its corresponding queue. The per-flow reservation state has to be installed by a setup protocol such as RSVP and retrieved during packet forwarding for scheduling calculations. All of these are a considerable challenge when operating at high speeds with a large number of flows.
Random Early Detection (RED) has been proposed as a replacement to the simple tail drop. See “Random Early Detection Gateways for Congestion Avoidance,”, by Sally Floyd et al., in IEEE/ACM Transactions on Networking, August 1993. RED monitors the average queue size and probabilistically drops packets when the queue exceeds certain thresholds. By dropping packets before the buffer is full, RED provides an early signal to the end systems to back off. However, RED cannot ensure fairness among competing flows. Flow Random Early Discard (FRED) improves the fairness of bandwidth allocation in RED by maintaining state for any backlogged flows. See “Dynamics of Random Early Detection,” by Dong Lin et al in Proceedings of SIGCOMM '97, October 1997. FRED drops packets from flows that have had many packets dropped in the past or flows that have queues larger than the average queue length.
In recent work published by Stoica et al. in “Core-Stateless Fair Queueing: Achieving Approximately Fair Bandwidth Allocations in High Speed Networks”, Proceedings of SIGCOMM '98, September, 1998, a Core-Stateless Fair Queueing (CSFQ) scheme was proposed to approximate fair bandwidth sharing without per-flow state in the interior routers. The main idea behind the CSFQ architecture is to keep per-flow state at slower edge routers and carry that information in packets to the core. Specifically, packets are labeled with flow arrival rate; core routers estimate the fair share and probabilistically drop packets whose arrival rate (as marked) exceeds the fair share. Through simulations, CSFQ was shown to achieve a reasonable degree of fairness: CSFQ tends to approach the fairness of Deficit Round Robin (DRR) (see “Efficient Fair Queuing using Deficit Round Robin,” by M. Shreedhar et al., in Proceedings of SIGCOMM '95, September 1995, and to offer considerable improvement over FIFO or Random Early Detection (RED)(see “Random Early Detection Gateways for Congestion Avoidance,” by Sally Floyd et al., in IEEE/ACM Transactions on Networking, August 1993. While CSFQ may offer great promise for making fair bandwidth sharing feasible in high-speed networks, it has disadvantages, because it requires estimation of fair share, and such estimation is very complex and difficult.
Another technique which has been suggested in the context of congestion control of multicast video and audio streams, relates to layering. In these layering schemes, video or audio traffic is usually divided into a small number of layers, typically through sub-band encoding. Receivers can choose the number of layers of traffic to receive based on the bandwidth available to them. Such an approach has been considered for video in “Thin Streams: An Architecture for Multicasting Layered Video,” by L. Wu et al., in NOSSDAV '97, May 1997, and for bulk-data transfer in “One to Many Reliable Bulk-Data Transfer in the Mbone,” by Lorenzo Vicisano et al., in Proceedings of the Third International Workshop on High Performance Protocol Architectures HIPPARCH '97, June 1997 and “Multiple-Channel Multicast Scheduling for Scalable Bulk-Data Transport,” by Michael Donahoo et al., in Infocom '99, March 1999. These approaches require that the content of the multicast video and audio streams be examined, and then processed or sliced such that more important information (such as reference or base level information) is differentiated from less important information (such as differential information representing only changes or differences between the current value and the reference or base level information). This is done so that the layers containing the less important information can be discarded first, in the event of congestion.